package 回溯.排列;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/22 10:05
 */
public class lc967连续差相同的数字 {


    /*
    这种不算严格意义上的全排列下`下`
     这种做法, 就有点意思了, 将 for 直接提到外面去
     */

    public void recursion(int index, int pre,int val, int n, int k, List<Integer> ans) {
        if (index == n) {
            ans.add(val);
            return;
        }
        if(pre + k <= 9){
            recursion(index + 1,pre + k, val * 10 + pre + k,n,k,ans);
        }
        // 这里特判  一下 k , 如果 k = 0 就不用计算了, 因为 上面的递归已经计算过了!
        if(pre - k >= 0 && k != 0){
            recursion(index + 1,pre - k,val * 10 + pre - k,n,k,ans);
        }

    }
    public int[] solve1(int n, int k) {
        List<Integer> ans = new ArrayList<>();

        for(int i = 1;i <= 9;i++){
            recursion(1,i,i,n,k,ans);
        }

        int[] res = new int[ans.size()];
        int index = 0;
        for (int num : ans) {
            res[index++] = num;
        }

        System.out.println(Arrays.toString(res));
        return res;
    }



    /*
     这个题 还有一种 更 巧妙的递归做法,  就是把 for 循环直接 提到 递归的外面去
     这种思想, 还是 挺妙的
     */
    public void recursion(int index, int n, int k, StringBuilder path, List<Integer> ans) {
        if (path.length() == n) {
            ans.add(Integer.parseInt(path.toString()));
            return;
        }

        for (int i = 0; i <= 9; i++) {
            if (i == 0 && path.length() == 0) {
                continue;
            }
//            int temp = path.charAt(path.length() - 1) - '0';
            if (path.length() == 0 || Math.abs(path.charAt(path.length() - 1) - '0' - i) == k) { // 根据上一个元素判断,当前是否可以选择
                path.append(i);
                recursion(index, n, k, path, ans);
                path.deleteCharAt(path.length() - 1);
            }
        }
    }

    public int[] solve(int n, int k) {
        List<Integer> ans = new ArrayList<>();
        recursion(0, n, k, new StringBuilder(), ans);


        int[] res = new int[ans.size()];
        int index = 0;
        for (int num : ans) {
            res[index++] = num;
        }
        return res;
    }


    @Test
    public void test() {
        System.out.println(solve1(3, 7));
    }
}
